Sort List

LeetCode 148 | Difficulty: Medium

Medium

Problem Description

Given the head of a linked list, return *the list after sorting it in ascending order*.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Constraints:

- The number of nodes in the list is in the range `[0, 5 * 10^4]`.

- `-10^5 <= Node.val <= 10^5`

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Topics: Linked List, Two Pointers, Divide and Conquer, Sorting, Merge Sort

---

Approach

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 198 ms)

Metric	Value
Runtime	198 ms
Memory	N/A
Date	2017-10-06

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode SortList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode s = head, f = head, prev = null; 
        while (f != null && f.next != null)
        {
            prev = s;
            s = s.next;
            f = f.next.next;
        }
        
        prev.next = null;
        var h1 = SortList(head);
        var h2 = SortList(s);
        return Merge(h1, h2);
    }

    private static ListNode Merge(ListNode h1, ListNode h2)
    {
        ListNode dummy = new ListNode(Int32.MinValue);
        ListNode tail = dummy;
        while (h1 != null && h2 != null)
        {
            if (h1.val < h2.val)
            {
                tail.next = h1;
                h1 = h1.next;
            }
            else
            {
                tail.next = h2;
                h2 = h2.next;
            }
            tail = tail.next;
        }
        if (h1 != null)
            tail.next = h1;
        if (h2 != null)
            tail.next = h2;
        
        return dummy.next;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.